//
// Created by xili on 2024/9/9 15:04.
// GO BIG OR GO HOME.
//
#include "leetcode.h"

//暴力递归
class Solution {
public:
    int minPathSum(vector <vector<int>> &grid) {
        return dfs(grid, grid.size() - 1, grid[0].size() - 1);
    }

    int dfs(vector <vector<int>> &grid, int i, int j) {
        if (i == 0 && j == 0) {
            return grid[0][0];
        }
        int up = INT32_MAX;
        int left = INT32_MAX;
        if (i > 0) {
            up = dfs(grid, i - 1, j);
        }
        if (j > 0) {
            left = dfs(grid, i, j - 1);
        }
        return grid[i][j] + min(up, left);
    }
};

//记忆化搜索
class Solution2 {
public:
    int minPathSum(vector <vector<int>> &grid) {
        vector <vector<int>> dp(grid.size(), vector<int>(grid[0].size(), -1));
        return dfs(grid, dp, grid.size() - 1, grid[0].size() - 1);
    }

    int dfs(vector <vector<int>> &grid, vector <vector<int>> &dp, int i, int j) {
        if (i == 0 && j == 0) {
            return grid[0][0];
        }
        if (dp[i][j] != -1) {
            return dp[i][j];
        }
        int up = INT32_MAX;
        int left = INT32_MAX;
        if (i > 0) {
            up = dfs(grid, dp, i - 1, j);
        }
        if (j > 0) {
            left = dfs(grid, dp, i, j - 1);
        }
        dp[i][j] = grid[i][j] + min(up, left);
        return dp[i][j];
    }
};

//严格位置依赖动态规划
class Solution3 {
public:
    int minPathSum(vector <vector<int>> &grid) {
        int n = grid.size();
        int m = grid[0].size();
        vector <vector<int>> ans(n, vector<int>(m));
        ans[0][0] = grid[0][0];
        for (int i = 1; i < n; i++) {
            ans[i][0] = grid[i][0] + ans[i - 1][0];
        }
        for (int i = 1; i < m; i++) {
            ans[0][i] = grid[0][i] + ans[0][i - 1];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                ans[i][j] = grid[i][j] + min(ans[i - 1][j], ans[i][j - 1]);
            }
        }
        return ans[n - 1][m - 1];
    }
};